#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef double db;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); }
	return x*f;
}
const int MAXN=60;
int n,m,k,head[MAXN<<1],dis[MAXN<<1],cnt,S,T,flow,cost;
bool vis[MAXN<<1];
struct edge
{
	int v,next,flow,cost;
}e[MAXN*100];
void addedge(int x,int y,int f,int c)
{
	e[cnt]=(edge){y,head[x],f,c};
	head[x]=cnt++;
	swap(x,y);
	e[cnt]=(edge){y,head[x],0,-c};
	head[x]=cnt++;
	return;
}
int aug(int u,int _min)
{
	vis[u]=true;
	if(u==T)
	{
		cost+=dis[S]*_min;
		flow+=_min;
		return _min;
	}
	int ret=0,k;
	for(int i=head[u];~i;i=e[i].next)
	{
		int v=e[i].v;
		if(vis[v]||!e[i].flow||dis[v]-dis[u]+e[i].cost)continue;
		k=aug(v,min(_min-ret,e[i].flow));
		e[i].flow-=k;
		e[i^1].flow+=k;
		ret+=k;
		if(ret==_min)break;
	}
	return ret;
}
bool mdf()
{
	int _min=INF;
	for(int u=S;u<=T;++u)
	{
		if(!vis[u])continue;
		for(int i=head[u];~i;i=e[i].next)
		{
			int v=e[i].v;
			if(vis[v]||!e[i].flow)continue;
			_min=min(_min,dis[v]-dis[u]+e[i].cost);
		}
	}
	if(_min==INF)return false;
	for(int i=S;i<=T;++i)
		if(vis[i])dis[i]+=_min;
	return true;
}
void zkw()
{
	flow=cost=0;
	memset(dis,0,sizeof(dis));
	do do memset(vis,0,sizeof(vis));
	while(aug(S,INF));
	while(mdf());
	return;
}
int main()
{
	int TT=read();
	for(int Case=1;Case<=TT;++Case)
	{
		n=read();m=read();k=read();
		int sum=0;
		memset(head,-1,sizeof(head));cnt=0;
		T=n<<1|1;
		for(int i=1;i<=n;++i)
		{
			int x=read();sum+=x;
			addedge(S,(i<<1)-1,x,0);
			addedge((i<<1),T,x,0);
		}
		for(int i=1;i<=m;++i)
		{
			int l=read(),p=read();
			addedge(S,2,l,p);
		}
		for(int i=1;i<=k;++i)
		{
			int d=read(),q=read();
			for(int j=1;j<=n-d-1;++j)
				addedge((j<<1)-1,j+d+1<<1,INF,q);
		}
		for(int i=1;i<n;++i)
		{
			addedge((i<<1)-1,(i+1<<1)-1,INF,0);
			addedge(i<<1,i+1<<1,INF,0);
		}
		zkw();
		if(flow<sum)printf("Case %d: impossible\n",Case);
		else printf("Case %d: %d\n",Case,cost);
	}
	return 0;
}
